#include <bits/stdc++.h>

using namespace std;

const int mod=10007;
int fac[mod],inv[mod];

typedef long long ll;

inline int qpow(int base,int exp){
    int ans=1;
    while(exp){
        if(exp&1) ans=(ll)ans*base%mod;
        base=(ll)base*base%mod;
        exp>>=1;
    }
    return ans;
}

inline void init(){
    fac[0]=1;
    for(int i=1;i<mod;i++) fac[i]=(ll)fac[i-1]*i%mod;
    inv[mod-1]=qpow(mod-1,mod-2);
    for(int i=mod-2;i>0;i--) inv[i]=(ll)inv[i+1]*(i+1)%mod;
    inv[0]=1;
}

inline void mul(int &x,int y){x=(ll)x*y%mod;}

inline int combination(int n,int m){
    int ans=1;
    while(n&&m){
        int nn,mm;
        nn=n%mod;mm=m%mod;
        if(nn<mm) ans=0;
        n/=mod;m/=mod;
        mul(ans,(ll)fac[nn]*inv[mm]%mod);
        mul(ans,inv[nn-mm]);
    }
    return ans;
}

inline int read(){
    int r;char c;bool f=0;
    for(c=getchar();c>'9'||c<'0';c=getchar()) if(c=='-') f=1;
    for(r=0;c<='9'&&c>='0';c=getchar()) r=r*10+c-'0';
    if(f) return -r;
    else return r;
}

int main(){
    int T;
    T=read();
    init();
    while(T--){
        int n,m;
        n=read();m=read();
        printf("%d\n",combination(n,m));
    }
}
